package com.yoshino.leetcode.interview150.binaryTree;

import java.util.Deque;
import java.util.LinkedList;

class BSTIterator {

    private TreeNode cur;
    private Deque<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        cur = root;
        stack = new LinkedList<>();
    }
    
    public int next() {
        // 中序
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        int val = cur.val;
        cur = cur.right;
        return val;
    }
    
    public boolean hasNext() {
        return !stack.isEmpty() || cur != null;
    }
}